#include "./listdefine.h" // 引入自己编写的 h 文件

/**
 * https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/
 * 循环链表插入
 */

// 创建循环链表
CircularLinkList createCircularList();
// 创建空循环链表
CircularLinkList createEmptyList();

// 创建带头结点的循环链表
CircularLinkList createListHasHead();

// 新增结点
void push(CircularLinkList *L, char data);
// 删除结点
void deleteNode(CircularLinkList *L, char value);

// 带头结点递减非空循环链表，插入结点且保持有序性. 
void insertCircularList(CircularLinkList *L, char x)
{
    ListNode *cur = *L;
    // 指定开始结点
    ListNode *net = cur->next;
    // 申请新结点存储空间
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->data = x;

    // net != L 说明还未到循环的结点
    while (net->data > x && net != (*L))
    {
        // printf("compare==>%c > %c >> %d\n", cur->data, x, cur->data > x);
        cur = cur->next;
        net = net->next;
    }

    cur->next = newNode;
    newNode->next = net;
}

// 循环有序链表插入
ListNode *insert(ListNode *head, char insertVal)
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = insertVal;
    node->next = NULL;

    // 若参数链表为空链表
    if (head == NULL)
    {
        // 则生成一个结点的单循环链表
        node->next = node;
        return node;
    }
    // 若参数链表是 一个结点的单循环链表，则将插入值放在下一个结点中
    if (head->next == head)
    {
        head->next = node;
        node->next = head;
        return head;
    }

    // 若参数链表是大于1个结点的链表，则定义两个结点指针: 一个当前结点指针，(当前指针的)下一个结点指针
    ListNode *curr = head;
    ListNode *next = head->next;

    // 若两个结点指针相等，则表示单循环链表遍历完毕。 判断插入在两个结点间 或者 在两结点外
    while (next != head)
    {
        // 若当前结点的值,在两个结点指针之间，则跳出循环 1< 2 < 3
        if (insertVal >= curr->data && insertVal <= next->data)
        {
            break;
        }

        // 当前结点值大于下一个结点值  3 1。 则 插入值大于当前结点值 或者 插入值小于当前结点值 跳出循环
        if (curr->data > next->data)
        {
            if (insertVal > curr->data || insertVal < next->data)
            {
                break;
            }
        }

        // 两个结点同时移动一个结点
        curr = curr->next;
        next = next->next;
    }

    // 当前结点指针的下一个结点指向 插入值的结点
    curr->next = node;
    // 插入值的结点指针 指向 下一个结点指针
    node->next = next;
    return head;
}

// 带头结点的单循环链表，删除相同的多余元素
void deleteSameElement(CircularLinkList L)
{
    ListNode *q;
    ListNode *p = L->next;
    while (L != p)
    {
        q = p->next;
        while (q != L && q->data == p->data)
        {
            p->next = q->next;
            free(q);
            q = p->next;
        }
        p = p->next;
    }
}


void deleteSameElement2(CircularLinkList L)
{
    // 慢指针 和 快指针
    ListNode *slow = L->next;
    ListNode *fast = L->next;
    // 不相等则说明末尾结点
    while (L != fast)
    {
        printf("fast=%c, slow=%c\n", fast->data,  slow->data);
        if (fast->data != slow->data)
        {
            // 慢指针: 当快慢指针指向的值不一致时，则将慢指针的下个结点指向快指针，然后慢指针移动一次
            slow->next = fast;
            slow = slow->next;
        }
        // 快指针每次都移动一次
        fast = fast->next;
        printElements(fast);
    }
}


void addBegin(CircularLinkList *L, char data)
{
    if ((*L) == NULL)
    {
        printf("addBegin>>> list not allow null");
        return;
    }
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    node->next = (*L)->next;
    (*L)->next = node;
}

void addEnd(CircularLinkList *L, char data)
{
    if ((*L) == NULL)
    {
        printf("addEnd>>> list not allow null");
        return;
    }
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    node->next = (*L)->next;
    (*L)->next = node;
    (*L) = node;
}

int main()
{
    // CircularLinkList CLL = createCircularList();
    // printCircularList(CLL);

    // 带头结点
    CircularLinkList CLL = createListHasHead();
    printCircularList(CLL);
    // insertCircularList(&CLL, '6');

    // addBegin(&CLL, '7');
    // addEnd(&CLL, '8');
    deleteSameElement(CLL);
    printCircularList(CLL);
    return 0;
}

CircularLinkList createCircularList()
{
    printf(">>>input circularlist element: ");
    // 分配内存地址，开始结点
    ListNode *start = (ListNode *)malloc(sizeof(ListNode));
    start->data = getchar();
    // 结束结点等于开始结点
    ListNode *end = start;
    // 定义新的结点
    ListNode *p;

    char ch;
    while ((ch = getchar()) != '\n')
    {
        p = (ListNode *)malloc(sizeof(ListNode));
        p->data = ch;
        // 第一次循环相当于 start->next = p; 下一次循环 (上次的p)->next = p
        end->next = p;
        //
        end = p;
    }
    // 最后一个结点 下一个结点 是开始结点
    end->next = start;

    // CircularLinkList head = NULL;
    // ListNode *end;
    // ListNode *p;
    // char ch;
    // while ((ch = getchar()) != '\n')
    // {
    //     p = (ListNode *)malloc(sizeof(ListNode));
    //     p->data = ch;
    //     if(head == NULL){
    //         head = p;
    //     }else{
    //         end->next = p;
    //     }
    //     end = p;
    // }
    // end->next = head;
    return start;
}

CircularLinkList createEmptyList()
{
    CircularLinkList L = (CircularLinkList)malloc(sizeof(ListNode));
    L->next = L;
    return L;
}

CircularLinkList createListHasHead()
{
    // 申请头结点，分配空间. 头结点不设置数据
    CircularLinkList head = (ListNode *)malloc(sizeof(ListNode));
    // head->data = 'h';

    ListNode *tail = head;
    ListNode *p;
    char ch;
    while ((ch = getchar()) != '\n')
    {
        // 申请新结点
        p = (CircularLinkList)malloc(sizeof(ListNode));
        p->data = ch;
        // 新结点链接的尾结点
        tail->next = p;
        // 尾指针指向新结点
        tail = p;
    }

    // 终端结点指针域指向头结点
    tail->next = head;

    return head;
}

void push(CircularLinkList *L, char data)
{
    ListNode *node = (CircularLinkList)malloc(sizeof(ListNode));
    node->data = data;

    if ((*L) == NULL)
    {
        node->next = node;
    }
    else
    {
        // 将新结点链接到链表
        node->next = (*L);
        // 遍历至链表的末尾结点
        ListNode *lastNode = (*L);
        while (lastNode->next != (*L))
        {
            lastNode = lastNode->next;
        }
        // 末尾结点的指向新结点
        lastNode->next = node;
    }

    // 将新结点置为开始结点
    (*L) = node;
}

void deleteNode(CircularLinkList *head, char key)
{

    // 链表是空则直接返回
    if (head == NULL)
        return;

    // 若链表只有一个结点，且需要删除的值，则释法莲表
    if ((*head)->data == key && (*head)->next == *head)
    {
        free(*head);
        *head = NULL;
        return;
    }

    ListNode *last = *head, *d;

    // If head is to be deleted
    if ((*head)->data == key)
    {

        // Find the last node of the list
        while (last->next != *head)
        {
            last = last->next;
        }

        // Point last node to the next of head i.e. the second node of the list
        last->next = (*head)->next;
        free(*head);
        *head = last->next;
        return;
    }

    // Either the node to be deleted is not found or the end of list is not reached
    while (last->next != *head && last->next->data != key)
    {
        last = last->next;
    }

    // If node to be deleted was found
    if (last->next->data == key)
    {
        d = last->next;
        last->next = d->next;
        free(d);
    }
    else
        printf("Given node is not found in the list!!!\n");
}
